﻿#include<iostream>
using namespace std;
//#include<algorithm>
//#include<list>
#include<vector>
#include<string>
#include<stack>
#include<queue>


//224.基本计算器
//https://leetcode.cn/problems/basic-calculator/

class Solution { //参考官方巧解
public:
    int calculate(string s)
    {
        int ret = 0;
        stack<int> nums; //符号栈，存储正负符号(+ - 1)
        int oper = 1; //符号默认为正
        nums.push(1);//开始默认为正+
        int i = 0;
        int n = s.size();
        while (i < n)
        {
            if(s[i] == ' ') {++i; continue;}
            if (s[i] == '+') //遇到+号表示下一个可能会进行运算，更新+符号
            {
                oper = nums.top();
                ++i;
            }
            else if (s[i] == '-') //遇到-号表示下一个可能会进行运算，更新-符号
            {
                oper = -nums.top();
                ++i;
            }
            else if (s[i] == '(')
            {
                nums.push(oper);//如果遇到括号则存入当前的符号，再进入括号中计算(这样，如果是负号那么括号中的所有数都会取反)
                ++i;
            }
            else if (s[i] == ')')
            {
                nums.pop(); //出当前括号前面的符号，接着正常运算
                ++i;
            }
            else //遇到数了
            {
                long num = 0;
                while (i < n && s[i] <= '9' && s[i] >= '0')
                {
                    num = num * 10 + (s[i] - '0') * oper;//开始取数，逐位取数
                    ++i;
                }
                ret += num;
            }
        }
        return ret;//为了防止一开始就在括号外加负号，最后还需要取一下符号
    }
};